class HNode {
    constructor (weight, parent, lchild, rchild) {
        this.weight = weight
        this.parent = parent || -1
        this.lchild = lchild || -1
        this.rchild = rchild || -1
    }
}

class HuffmanTree {
    /**
     * 创建哈夫曼树
     * 由哈夫曼树性质可知n个叶子结点就共有 2n - 1个节点 
     * @param {*} n 权值列表 
     */
    constructor (list) {
        let n = list.length
        if (n <= 1) return
        let m = 2*n - 1
        this.tree = new Array(m)

        for (let i = 0; i < n; i++) {
            const node = new HNode(list[i])
            this.tree[i] = node
        }
        for (let i = n; i < m; i++) {
            const node = new HNode(0)
            this.tree[i] = node
        }

        for (let i = n; i < m; i++) {
            let m1 = 1000, m2 = 1000
            let x1 = 0, x2 = 0
            for (let j = 0; j < i; j++) {              
                if (this.tree[j].parent == -1 && this.tree[j].weight < m1) {
                    m2 = m1;
                    x2 = x1;
                    m1 = this.tree[j].weight
                    x1 = j
                } else if (this.tree[j].parent == -1 && this.tree[j].weight < m2) {
                    m2 = this.tree[j].weight
                    x2 = j
                }
            }
            this.tree[x1].parent = i
            this.tree[x2].parent = i
            this.tree[i].lchild = x1
            this.tree[i].rchild = x2
            this.tree[i].weight = m1 + m2
        }
    }
}

const h = new HuffmanTree([10, 20, 40, 50])
console.log(JSON.stringify(h.tree))